package Test;

import java.util.HashMap;

public class 最小覆盖滑动窗口问题 {
    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>(),window=new HashMap<>();
        for(char c:t.toCharArray()){
            int num=need.getOrDefault(c,0);
            need.put(c,num++);
        }

        int start=0;
        int left=0,right=0;
        int vaild=0;
        int len=Integer.MAX_VALUE;
        while (right<s.length()){
            char c=s.charAt(right);
            right++;
            if(need.containsKey(c)){
                int num=window.getOrDefault(c,0);
                window.put(c,num++);
                if(window.get(c).equals(need.get(c))){
                    vaild++;
                }
            }
            System.out.println("left"+left+"   right"+right);
            while (vaild==t.length()){
                if(right-left<len){
                    start=left;
                    len=right-left;
                }
                char d=s.charAt(left);
                left++;
                if(need.containsKey(d)){
                    int num=window.getOrDefault(d,0);
                    window.put(d,num--);
                    if(window.get(d).equals(need.get(d))){
                        vaild--;
                    }
                }
            }
        }
        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }
    public static void main(String[] args) {
        System.out.println("minWindow() = " + minWindow("ODEBANC", "ABC"));

    }
}
